package com.shuang.link5;

public class RemoveNthFromEnd {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //快慢指针

        //虚拟头节点
        ListNode vHead = new ListNode(0, head);

        //快慢指针都先指向虚拟头节点
        ListNode fast = vHead;
        ListNode slow = vHead;

        //快指针先走n+1步 然后 快慢同时走，直到快的走到null时慢指针正好指向倒数第n个位置的前面一个位置在进行删除元素即可
        //快的先走
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        //快慢再同时走
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        //此时慢指针指向倒数第n个元素位置的前一个位置 删除倒数第n个元素
        //判断一下 避免空指针异常
        if (slow.next != null) {
            slow.next = slow.next.next;
        }

        return vHead.next;

    }
}
